package com.ljc;

import java.util.*;

/**
 * @author ljchen on 2022/1/19
 * Given an integer array nums and an integer k, return true if there are two
 * distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
 */
public class E219ContainsDuplicateII {

    public static void main(String[] args) {
        int[] nums = new int[]{0, 1, 2, 3, 4, 1, 2, 2};
        int k = 5;
        boolean result = containsNearbyDuplicate(nums, k);
        System.out.println(result);
    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, List<Integer>> res = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!res.containsKey(nums[i])) {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                res.put(nums[i], list);
            } else { //将原来的数据加入到新的list当中来
                List<Integer> list = new ArrayList<>(res.get(nums[i]));
                list.add(i);
                res.put(nums[i], list);
            }
        }
        for (Map.Entry<Integer, List<Integer>> entry : res.entrySet()) {
            List<Integer> list = entry.getValue();
            if (list.size() >= 2) {
                for (int i = 0; i < list.size(); i++) {
                    for (int j = i + 1; j < list.size(); j++) {
                        if (Math.abs(list.get(i) - list.get(j)) <= k) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

}